棧是一種線性表,它的特點是什麼? ?
棧是一種線性表,它的特點是什麼?
棧(stack)在電腦科學中是限定僅在表尾進行插入或刪除操作的線形表。
棧是一種資料結構,它按照先進後出的原則儲存資料,先進入的資料被壓入棧底,最後的資料在棧頂,需要讀資料的時候從棧頂開始彈出資料(最後一個數據被第一個讀出來)。
棧是隻能在某一端插入和刪除的特殊線性表。用桶堆積物品,先堆進來的壓在底下,隨後一件一件往堆。取走時,只能從上面一件一件取。堆和取都在頂部進行,底部一般是不動的。
棧就是一種類似桶堆積物品的資料結構,進行刪除和插入的一端稱棧頂,另一堆稱棧底。插入一般稱為進棧(PUSH),刪除則稱為退棧(POP)。 棧也稱為後進先出表(LIFO表)。
1、進棧(PUSH)演算法
①若TOP≥n時,則給出溢位資訊,作出錯處理(進棧前首先檢查棧是否已滿,滿則溢位;不滿則作②);
②置TOP=TOP+1(棧指標加1,指向進棧地址);
③S(TOP)=X,結束(X為新進棧的元素);
2、退棧(POP)演算法
①若TOP≤0,則給出下溢資訊,作出錯處理(退棧前先檢查是否已為空棧, 空則下溢;不空則作②);
②X=S(SOP),(退棧後的元素賦給X);
③TOP=TOP-1,結束(棧指標減1,指向棧頂)。
棧和佇列都是特殊線性表,簡述他們的區別(特殊性)
棧是先進後出,隊是先進先出,這是他們存取上的根本不同
棧和線性表有什麼區別?
一般線性表使用陣列來表示的
線性表一般有插入、刪除、讀取等對於任意元素的操作
而棧只是一種特殊的線性表
棧只能在線性表的一端插入(稱為入棧,push)或者讀取棧頂元素或者稱為“彈出、出棧”(pop)。
棧在陣列的基礎上可以用一個指向棧頂的標駭符來表示,如a表示棧,則a[top]就表示棧頂元素
棧就是所謂的“先進後出,First in last out, FILO”
堆疊是一種結構較簡單的線性表,它只允許在表的一端進行資料的插入和刪除操作 20分
// stack.h: header file
class Stack {
int MaxStack;
int EmptyStack; int top;
char* items;
public:
Stack(int);
~Stack();
void push(char);
char pop();
int empty();
int full();
};
-------------------------------
// stack.cpp: stack functions
#include "stack.h"
Stack::Stack(int size) {
MaxStack = size;
EmptyStack = -1;
top = EmptyStack;
items = new char[MaxStack];
}
Stack::~Stack() {delete[] items;}
void Stack::push(char c) {
items[++top] = c;
}
char Stack::pop() {
return items[top--];
}
int Stack::full() {
return top + 1 == MaxStack;
}
int Stack::empty() {
return top == EmptyStack;
}
-------------------------------
// stackmain.cpp: use stack
#include
#include "stack.h"
int main() {
Stack s(10); // 10 chars
char ch;
while ((ch = cin.get()) != '\n')
if (!s.full()) s.push(ch);
while (!s.empty())
cout << s.pop();
cout << endl;
return 0;
}
串是一種特殊的線性表,其特殊性體現在什麼地方
串是一種特殊的線性表,其特殊性體現在資料元素是一個字元
串值也可用連結串列來儲存,由於串的資料元素是一個字元,它只有8位二進位制數, 因此用連結串列儲存時,通常一個結點中存放的不是一個字元,而是一個子串,例如: 在編輯系統中,整個文字編輯區可以看成是一個串,每一行是一個子串,構成一個結點。
棧和線性表有什麼區別
一般線性表使用陣列來表示的
線性表一般有插入、刪除、讀取等對於任意元素的操作
而棧只是一種特殊的線性表
棧只能在線性表的一端插入(稱為入棧,push)或者讀取棧頂元素或者稱為“彈出、出棧”(pop)。
棧在陣列的基礎上可以用一個指向棧頂的識別符號來表示,如a表示棧,則a[top]就表示棧頂元素
棧就是所謂的“先進後出,First in last out, FILO”
( )是一種先進先出的線性表。 A 棧 B佇列 C雜湊表(散列表) D二叉樹
B 佇列
棧的概念是彈壓,就像子彈殼裝彈,一粒一粒壓進去,但是打出來的時候是從上面打駭來的,最先壓進去的最後彈出來,如果進去順序是123,打出來順序是321,這就是後進先出
佇列的概念就是我們平時排隊,按次序來,你排在第1個,那你就第一個輪到,就是先進先出,先到先來
棧是插入和刪除只能固定在一端進行的線性表,也稱“後進先出表”。
有2個問題需要澄清:
1.棧是一種後進先出的資料結構,只能在末端進行插入和刪除的操作。應該說成是隻能線上性表的一端進行插入和刪除。說成末端,就認為的把線性表分成開始端和結束端了。但由於線性表中元素只具有線性關係,並沒有明確的起始元素和終止元素。
2.函式呼叫之所以需要棧,是因為函式執行過程中,還能會巢狀呼叫其他函式,但無論巢狀呼叫多少個函式,總是要遵循一個原則:後被呼叫的函式要先執行完畢,程式要回到上一層函式的呼叫處繼續執行,為了實現這個機制,才設計了棧這種後進先出的資料結構。如果把函式呼叫看成羅餐盤的話,而把當你去盤子的時候,肯定先取走最後一個羅上去的盤子,那麼函式執行結束,函式呼叫返回就相當於你在取盤子。