天天看點
傳回

C++ 堆棧 stack堆棧

[TOP]

     ~~~~     棧和隊列是兩種重要的線性結構，是很常用的資料結構。從資料結構的角度看，棧和隊列也是線性結構，其特殊性在于棧和隊列的基本操作是線性表操作的子集，它們是操作受限的線性表，是以，可稱為限定性的資料結構。但是從資料類型角度看，它們是和線性表大不相同的兩類重要的抽象資料類型。由于它們廣泛應用在各種軟體系統中，是以在面向對象的程式設計中，它們是多型資料類型。

這裡我們隻學習堆棧。

堆棧

介紹

  • 堆棧（英語：stack）又稱為棧或堆疊，是計算機科學中的一種抽象資料類型，隻允許在有序的線性資料集合的一端（稱為堆棧頂端，英語：top）進行加入資料（英語：push）和移除資料（英語：pop）的運算。因而按照後進先出（LIFO, Last In First Out）的原理運作。

常與另一種有序的線性資料集合隊列相提并論，堆棧常用一維數組或連結清單來實作。

操作

堆棧使用兩種基本操作：推入（壓棧，push）和彈出（彈棧，pop）：

  • 推入：将資料放入堆棧頂端，堆棧頂端移到新放入的資料。
  • 彈出：将堆棧頂端資料移除，堆棧頂端移到移除後的下一筆資料。

特點

堆棧的基本特點：

  • 先入後出，後入先出。
  • 除頭尾節點之外，每個元素有一個前驅，一個後繼。

實作

堆棧實作一共有兩種方法，一種是數組，一種是連結清單，本來打算自己寫一個，後來考慮，我們應該先學習現有的，于是我去std裡面找stack，我們可以先看一看std的源碼。

template<typename _Tp, typename _Sequence = deque<_Tp> >
    class stack
    {
      // concept requirements
      typedef typename _Sequence::value_type _Sequence_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)

      template<typename _Tp1, typename _Seq1>
        friend bool
        operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);

      template<typename _Tp1, typename _Seq1>
        friend bool
        operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);

    public:
      typedef typename _Sequence::value_type                value_type;
      typedef typename _Sequence::reference                 reference;
      typedef typename _Sequence::const_reference           const_reference;
      typedef typename _Sequence::size_type                 size_type;
      typedef          _Sequence                            container_type;

    protected:
      //  See queue::c for notes on this name.
      _Sequence c;

     ~~~~     可以很明顯的發現，stl裡面的用的是一個deque的一個東西進行内部記憶體管理，而deque是一個雙端隊列。

     ~~~~     雙端隊列（deque，全名double-ended queue）是一種具有隊列和棧性質的抽象資料類型。雙端隊列中的元素可以從兩端彈出，插入和删除操作限定在隊列的兩邊進行。是不是很像雙向連結清單。

     ~~~~     我們可以發現stack預設是使用deque的，但是其實也是可以使用其他的容器，隻要對應的容器滿足一定的條件就可以了，這其實就是一個分比對器。

     ~~~~     下面就是一個C語言的stack，有兩種實作的方法，一種是數組堆棧，一種的串列堆棧，下面的是串列堆棧。

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define elemType int							/* 鍊棧元素資料類型，以整型為例 */
#define SNODE_SIZE sizeof (struct sNode)		/* 鍊棧結點空間大小 */

#define status int	/* 狀态型變量 */
#define OVERFLOW -1	/* 記憶體溢出狀态碼 */
#define ERROR 0		/* 錯誤狀态碼 */
#define OK 1		/* 正确狀态碼 */

/* 鍊棧結點存儲結構 */
typedef struct sNode {
	elemType data;
	struct sNode *next;
} sNode, *sNodePtr;

/* 鍊棧存儲結構 */
typedef struct linkStack {
	sNodePtr top; /* 棧頂指針 */
} linkStack;

/* 初始化 */
/* 操作結果：構造一個帶頭結點的空鍊棧S */
void initStack (linkStack *S) {
	S->top = (sNodePtr) malloc (SNODE_SIZE); /* 産生頭結點，棧頂指針指向此頭結點 */
	if (!S->top) /* 記憶體配置設定失敗 */
		exit (OVERFLOW);
	S->top->next = NULL;
}

/* 銷毀 */
/* 初始條件：鍊棧S已存在。操作結果：銷毀鍊棧S */
void destroyStack (linkStack *S) {
	sNodePtr p, q;
	
	p = S->top; /* p指向S的頭結點 */
	while (p) {
		q = p->next; /* q指向p的下一個結點 */
		free (p); /* 回收p指向的結點 */
		p = q; /* p移動到下一個結點 */
	} /* 直到沒有下一個結點 */
}

/* 清空 */
/* 初始條件：鍊棧S已存在。操作結果：将S重置為空棧 */
void clearStack (linkStack *S) {
	sNodePtr p, q;
	
	p = S->top->next; /* p指向棧的第一個結點 */
	while (p) {
		q = p->next; /* q指向p的下一個結點 */
		free (p); /* 回收p指向的結點 */
		p = q; /* p移動到下一個結點 */
	}  /* 直到沒有下一個結點 */
	
	S->top->next = NULL;
}

/* 判斷鍊棧是否為空 */
/* 初始條件：鍊棧S已存在。操作結果：若S為空鍊棧，則傳回TRUE，否則傳回FALSE */
status stackIsEmpty (linkStack *S) {
	return S->top->next == NULL;
}

/* 求鍊棧長度 */
/* 初始條件：鍊棧S已存在。操作結果：傳回S中資料元素個數 */
int stackLength (linkStack *S) {
    int i = 0;
    sNodePtr p;
	
	p = S->top->next; /* p指向棧的第一個結點 */
	while (p) { /* 未到棧尾 */
		i++;
		p = p->next;
    }
    
    return i;
}

/* 擷取棧頂元素 */
/* 初始條件：鍊棧S已存在。操作結果：當棧不為空時，将棧頂元素其值賦給e并傳回OK，否則傳回ERROR */
status getTopElem (linkStack *S, elemType *e) {
	sNodePtr p;
	
	if (stackIsEmpty (S))
		return ERROR;
	
	p = S->top->next; /* p指向棧的第一個結點 */
	*e = p->data;
	
	return OK;
}

/* 入棧 */
/* 操作結果：在S的棧頂插入新的元素e */
status push (linkStack *S, elemType e) {
	sNodePtr p;
	
	p = (sNodePtr) malloc (SNODE_SIZE); /* 産生新結點 */
	if (!p) /* 記憶體配置設定失敗 */
		exit (OVERFLOW);
	
	p->data = e;
	p->next = S->top->next; /* 将新結點連結到原棧頂 */
	S->top->next = p; /* 棧頂指向新結點 */
}

/* 出棧 */
/* 操作結果：删除S的棧頂元素，并由e傳回其值 */
status pop (linkStack *S, elemType *e) {
	sNodePtr p;
	
	if (stackIsEmpty (S))
		return ERROR;
	
	p = S->top->next; /* p指向鍊棧的第一個結點 */
	*e = p->data; /* 取出資料 */
	S->top->next = p->next;
	free (p); /* 删除該結點 */
	
    if (S->top == p) /* 棧為空 */
    	S->top->next = NULL;
    
    return OK;
}

/* 列印棧内容 */
/* 初始條件：鍊棧S已存在。操作結果：當棧不為空時，列印棧内容并傳回OK，否則傳回ERROR */
status printStack (linkStack *S) {
	sNodePtr p;
	
	if (stackIsEmpty (S))
		return ERROR;
	
	p = S->top->next;
	while (p) {
		printf ("%d\t", p->data);
		p = p->next;
	}
	putchar ('\n');
	
	return OK;
}

我們實際使用還是會使用std::stack就可以了，當然我們也可以根據自身的要求重寫stack裡面預設的deque，來優化記憶體管理。

std::stack的調用還是很簡單的：

#include <iostream>
#include <stack>


int main(){
    std::stack<int> _t_stack;
    
    for(int i = 0; i < 10; i++){
        _t_stack.push(i);
        std::cout << "push data:" << i << std::endl;
    }

    while(!_t_stack.empty()){
        std::cout << "top data:" << _t_stack.top() << std::endl;
        _t_stack.pop();
    }
    return 1;
}

這是直接在windows上編譯了：

PS F:\C++\studytest\structure\test1> g++ -o test .\stack_test.cpp
PS F:\C++\studytest\structure\test1> .\test.exe
push data:0
push data:1
push data:2
push data:3
push data:4
push data:5
push data:6
push data:7
push data:8
push data:9
top data:9
top data:8
top data:7
top data:6
top data:5
top data:4
top data:3
top data:2
top data:1
top data:0
PS F:\C++\studytest\structure\test1>
基礎算法 c++ STL stack
上一篇: Stack 堆棧的實作
下一篇: stack堆棧容器stack堆棧容器

繼續閱讀