棧
棧:具有數(shù)據(jù)先入后出餐抢,先出后入的特性霍转。
從棧的操作特性上來看荐绝,棧是一種“操作受限”的線性表,只允許在一端插入和刪除數(shù)據(jù)避消。
當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)低滩,并且滿足后進(jìn)先出召夹、先進(jìn)后出的特性,我們就應(yīng)該首選“椝∧”這種數(shù)據(jù)結(jié)構(gòu)戳鹅。
棧既可以用數(shù)組來實(shí)現(xiàn),也可以用鏈表來實(shí)現(xiàn)昏兆。用數(shù)組實(shí)現(xiàn)的棧枫虏,我們叫作順序棧,用鏈表實(shí)現(xiàn)的棧爬虱,我們叫作鏈?zhǔn)綏隶债!?/p>
用數(shù)組實(shí)現(xiàn)順序棧
C代碼結(jié)構(gòu)體實(shí)現(xiàn)
#include<stdio.h>
#define maxsize 100
typedef struct{
int data[maxsize];
int topindex;
}SeqStack;
void push(SeqStack &stack, int value)
{
if(stack.topindex == maxsize){
printf("stack is full \n");
}else{
stack.data[stack.topindex] = value;
stack.topindex++;
}
}
void pop(SeqStack &stack)
{
if(stack.topindex == 0){
printf("stack is empty\n");
}else{
printf("pop %d\n", stack.data[--stack.topindex]);
}
}
int isEmpty(SeqStack &stack)
{
if(stack.topindex == 0){
printf("stack is empty\n");
return 1;
}else{
printf("stack is not empty \n");
return 0;
}
}
int main()
{
SeqStack stack;
stack.topindex = 0;
push(stack, 5);
push(stack, 4);
push(stack, 3);
pop(stack);
pop(stack);
isEmpty(stack);
pop(stack);
isEmpty(stack);
pop(stack);
return 0;
}
運(yùn)行結(jié)果
pop 3
pop 4
stack is not empty
pop 5
stack is empty
stack is empty
c++類對(duì)象實(shí)現(xiàn)棧
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
class Stack{
private:
int *data_;
int max_size_;
int top_;
void initStack(){
data_ = new int(max_size_);
top_ = -1;
}
public:
Stack(){
max_size_ = 10;
initStack();
}
Stack(int max_size){
max_size_ = max_size;
initStack();
}
~Stack(){
delete data_;
}
int isEmpty(){
return (top_ == -1) ? 1:0;
}
int isFull(){
return (top_ >= max_size_) ? 1:0;
}
int push(int x){
if(isFull()) return 0;
else data_[++top_] = x;
return 1;
}
int pop(int &x){
if(isEmpty()) return 0;
else x = data_[top_--];
return x;
}
void clear(){
top_ = -1;
}
};
int main()
{
Stack stack(12);
stack.push(123);
stack.push(123);
stack.push(456);
int a;
while(stack.pop(a)) {
cout<<a<<endl;
}
return 0;
}
支持動(dòng)態(tài)擴(kuò)容的棧
當(dāng)棧是由數(shù)組構(gòu)建時(shí),棧的內(nèi)存有一定的限制跑筝。當(dāng)棧內(nèi)存滿時(shí)死讹,我們需要對(duì)棧進(jìn)行動(dòng)態(tài)擴(kuò)容,這里只需要依賴一個(gè)可以動(dòng)態(tài)擴(kuò)容的數(shù)組即可曲梗,一個(gè)動(dòng)態(tài)擴(kuò)容的數(shù)組是當(dāng)數(shù)組空間不夠時(shí)赞警,我們就重新申請(qǐng)一塊更大的內(nèi)存,將原來數(shù)組中數(shù)據(jù)統(tǒng)統(tǒng)拷貝過去虏两。這樣就實(shí)現(xiàn)了一個(gè)支持動(dòng)態(tài)擴(kuò)容的數(shù)組愧旦。因此動(dòng)態(tài)擴(kuò)容的棧就是當(dāng)棧滿了之后,我們就申請(qǐng)一個(gè)更大的數(shù)組定罢,將原來的數(shù)據(jù)搬移到新數(shù)組中笤虫。
棧的應(yīng)用
- 函數(shù)調(diào)用
- 表達(dá)式求值:使用兩個(gè)棧,一個(gè)存儲(chǔ)操作數(shù)祖凫,一個(gè)存儲(chǔ)符合
- 括號(hào)匹配:棧來存儲(chǔ)未匹配的左括號(hào)琼蚯,掃描到右括號(hào)時(shí),左括號(hào)出棧并匹配惠况。
- 實(shí)現(xiàn)瀏覽器的前進(jìn)和后退