【C++】Stack and Queues

堆叠跟柱列在程序中算是很基本的资料结构~

它们的储存特性一个是LIFO~ 另一个则是FIFO~

学习目标: Stack and Queues的概念及实务

学习难度: ☆☆☆

堆叠的部分~ 我这边用变数(顶部索引)跟阵列(堆叠容器)的方式来实作~

实作的思维很简单~ 就是用变数存阵列顶部的索引~

例如~ 一个资料的堆叠顶部索引是1~ 两个资料的堆叠顶部索引是2~

当弹出一个资料时~ 堆叠顶部索引就要减少~

#include<iostream>

using namespace std;

int stack[105]; //整数的阵列 

int stack_top; //阵列的顶部 

int main ()
{
    string cmd; //输入的指令 
 
    int num; //输入的整数 

    stack_top = 0; //初始化阵列的顶部  

    while( cin >> cmd ) //当输入指令  
    {
        if( cmd == "push" )
        {
            cin >> num;
            
            stack[stack_top] = num;
            
            stack_top++;
        }
        
        else if( cmd == "pop" )
        {
            if( stack_top == 0 )
            {
            	cout << " nothing in stack" << endl;
			}                           
            else
            {
                cout << " pop from stack" << stack[stack_top-1] << endl;
                
                stack_top--;
            }
        }
        else
        {
           cout << " input error ";
        	
           main ();
		}
    }
    return 0;
}

在来看到柱列的部分~ 我这边是用queue的函式库~

所以说~ 这边只要专注於记忆queue的使用方式即可~

例如~ 柱列的宣告~ push~ back~ front~ pop~ 等~

另外~ 阵列印出的方式是用~front印~ 然後再pop~

#include <iostream>

#include <queue>

using namespace std;

int main() 
{
	
    queue<int> q;
    
    q.push(1); // q[1]
    
    q.push(2); // q[1, 2]
    
    q.push(4); // q[1, 2, 4]

    cout << q.front() << endl; // 1
    
    cout << q.back() << endl; // 4
    
    cout << q.size() << endl; // 3
    
    

    int value1 = q.front(); // copy q.front's integer to value1
    
    int &value2 = q.front(); // reference q.front's address to value2
   
    cout << value1 << " " << &value1 << endl; //这里的value1的地址不一样，因为它是用copy的
    
    cout << q.front() << " " << &q.front() << endl; 
    
    cout << value2 << " " << &value2 << endl; 
    

    // 印出 queue 内所有内容 (思维是印front，然後pop，在轮回直到结束~) 
    
    int size = q.size();
    
    for (int i = 0; i < size; i++) 
	{
        cout << q.front() << " ";
        
        q.pop();
    }
    
    cout << "\n";

    return 0;
}

参考资料:

https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/stack.html

https://shengyu7697.github.io/std-queue/