栈(Stack)

栈就是一种只允许在表尾进行插入和删除操作的线性表
is a linear data structure which operates in a LIFO(last in first out) or FILO(first in last out) pattern

如何理解栈的概念

 举一个生活中的例子:我在一个储物箱中,堆了一堆衣服,我的一件球衣在最下面,而我要拿这件衣服,就意味着我必须将上面的衣服全部拿出来才可以,但是由于箱子只有一个口,我也只能从上面拿东西,心里还默默想着,当初就不该将球衣早早的放进去,导致结果就是先进后出!

栈的术语说明

栈顶:允许进行插入和进行删除操作的一段成为栈顶
栈底:表的另一端称为栈底 (第一个元素进入的位置)
压栈:在栈顶位置插入元素的操作叫做压栈,或入栈、进栈
出栈:删除栈顶元素的操作叫做出栈,也叫作弹栈,或者退栈
空栈:不含元素的空表
栈溢出:当栈满的时候,如果再有元素压栈,则发生上溢,当栈空的时候,再出栈则发生下溢

栈的常见分类:

(1)基于数组的栈——以数组为底层数据结构时,通常以数组头为栈底,数组头到数组尾为栈顶的生长方向
(2)基于单链表的栈——以链表为底层的数据结构时,以链表头为栈顶,便于节点的插入与删除,压栈产生的新节点将一直出现在链表的头部

使用标准库的栈时, 应包含相关头文件,在栈中应包含头文件: #include< stack > 。定义:stack< int > s;

一、基于数组的栈的实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*  stack  */
#include <iostream>
using namespace std;
int top=-1;
int arr[5]={0};
bool isEmpty()
    { 
        if(top==-1)return true; 
        else return false;
    } 

bool isFull()
    { 
        if(top==4)return true; 
        else return false; 
    } 

void push(int value)
    { 
        if(isFull())
            { 
                cout<<"stack overFlow"<<endl;
            }
        else
           { 
                top++;
                arr[top]=value;
            } 
    } 

int pop(){ 
        if(isEmpty())
            { 
                cout<<"stack underflow"<<endl; 
                return 0; 
            } 
        else
            { 
                int popValue=arr[top]; 
                arr[top]=0; 
                top--; 
                return popValue; 
            } 
    } 

int count(){ 
    return top+1; 
           } 
           
int peek(int pos){ 
        if(isEmpty())
            {
                cout<<"stack underflow"<<endl; 
                return 0;
            }
        else
           { 
                return arr[pos];
            } 
    } 
    
 void change(int pos,int value)
        { 
            arr[pos]=value; 
            cout<<"item changed at location"<<pos<<endl; 
        } 

void display()
        { 
            cout<<"all values in the stack are "<<endl; 
            for (int i = top; i >=0; i--) 
                             { 
                                   cout<<arr[i]<<' '; 
                              } 
                              cout<<endl;
        }
    

int main()
{
    int option,position,value;
    do{
        cout<<"what operation do you want to perform? select option number."<<endl;
        cout<<"0. exit"<<endl;
        cout<<"1.push"<<endl;
        cout<<"2.pop"<<endl;
        cout<<"3.isEmpty"<<endl;
        cout<<"4.isFull"<<endl;
        cout<<"5.peek"<<endl;
        cout<<"6.cout"<<endl;
        cout<<"7.change"<<endl;
        cout<<"8.display"<<endl;
        cin>>option; 
        switch(option)
            { 
                 case 0: break; 
                 case 1: 
                        cout<<"enter an item to push in the stack"<<endl; 
                        cin>>value; 
                        push(value); 
                        break; 
                 case 2: 
                        cout<<"pop function called \n poped value: "<<pop()<<endl; 
                        break; 
                 case 3:
                        if(isEmpty())cout<<"stack is empty"<<endl; 
                        else cout<<"stack is not empty"<<endl; 
                        break; 
                 case 4: 
                        if(isFull())cout<<"stack is Full"<<endl; 
                        else cout<<"stack is not Full"<<endl; 
                        break; 
                 case 5: 
                        cout<<"enter position of item you want to peek: "<<endl; 
                        cin>>position; 
                        cout<<"peek function called value at position "<<position<<"is "<<peek(position)<<endl; 
                        break; 
                 case 6: 
                        cout<<"count function called,Number of Item in the stack are:"<<count()<<endl; break; 
                 case 7: 
                        cout<<"change function called"; cout<<"enter position of Item you want to change:";          
                        cin>>position; cout<<endl; cout<<"enter value of Item you want to change: ";    
                        cin>>value; change(position,value); 
                        break; 
                case 8: 
                        cout<<"display function called: "<<endl; 
                        display(); 
                        break; 
                default: 
                        cout<<"enter proper option Number"<<endl; 
        } 
    }while(option!=0); 
    return 0;
}

二、基于链表的栈实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/****************************************************************
 * C++ Stack implement using linkedlist
 * date: 2023-3-3
 * author : Alex Li
 * version : 1.2
 * ****************************************************************/

#include<iostream>
using namespace std;
//结点定义
struct Node{
	int data;//数据域
	Node *next;//指针域
};

Node *St=NULL;//定义指针,指向栈顶

//判断栈是否为空
bool IsEmpty(Node *S){
	if (S == NULL)return true;
	else return false;
}
//入栈
void Push(Node *S, int x){
    Node *NewNode;//新结点
	NewNode = new Node;//新结点申请内存
	NewNode->data = x;//新结点数据域赋值
	NewNode->next = NULL;//新结点指针域赋值
	if (IsEmpty(S)){//如果链栈为空
		S= NewNode;//链栈顶指针指向新结点
        }
	else{//如果链栈非空
		NewNode->next = S;//新结点前插入链栈
		S= NewNode;//更新栈顶指针
	}
    St=S;
}
//出栈
void Pop(Node *S){
    int x;
	if (IsEmpty(S))	{
		cout << "栈空,无法出栈" << endl;
		return; //什么都不做
	}
	Node *p = S;//定义探测指针p并指向栈顶结点
	if (p->next == NULL){//如果链栈仅含一个结点
		x = p->data;//获取栈顶结点值
		S = NULL;//置链栈为空
		delete p;//删除原栈顶结点
	}
	else{//如果链栈中至少含有两个结点
		x = p->data;//获取栈顶结点值
		S = S->next;//栈顶指针后移
		delete p;//删除原栈顶结点
	}
    cout<<"the value of pop element is: "<<x<<endl;
    St=S;
}
//输出链栈
void Display(Node *S){
	if (IsEmpty(S))//如果链栈为空
	{
		cout << "栈空,无结点输出" << endl;
		return;//什么都不做
	}
	Node *p = S;//定义探测指针p并指向栈顶结点
	while (p != NULL)
	{
		cout << p->data << "=>";//输出栈顶结点值
		p = p->next;//p后移
	}
	cout << "NULL" << endl;
}
//主程序
int main(){
	 Push(St, 1);//入栈
     Push(St, 2);//入栈
	 Display(St);
	 Pop(St);//出栈
	 Display(St);
	 Push(St, 3); //入栈
	 Display(St);
}

pop: to put or take something quickly 迅速地拿;快速地放
peek: to look at something for a shorttime 匆匆一瞥

Scroll to Top