プログラミングC: 投稿 15 – スタックをインストールします。 (スタック)

スタック (スタック) 挿入および削除がリストの最後に行われ、我々は先端これを呼び出すことができます順不同リストです (トップ) スタック

スタック

この記事では、配列ポインタにインストールし、スタックにする方法を学ぶ

1. スタックアレイにインストール

#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
	int Top; //Dinh Top
	item Data[Max]; //Mang cac phan tu
};

1.1 空のリストを初期化します, チェックリストは空です, フル

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = 0; //Stack rong khi Top la 0
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == 0);
}

int Isfull(Stack S) //kiem tra Stack day
{
	return (S.Top == Max); //
}

1.2 スタックに要素を追加 (押す)

要素を挿入するには1場所スタックトップに挿入, トップアップと葬儀 1 ユニット
押す

void Push(Stack &S, item x) //them phan tu vao Stack
{
	if (!Isfull(S))
	{
		S.Data[S.Top] = x; //Gan du lieu
		S.Top ++; //Tang Top len 1
	}
}

1.3 トップ上のデータを取得しますが、削除されていない (ピーク)

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Data[S.Top-1]; //Lay du lieu tai Top
}

1.4 取り外し、上部のデータを取得する (ポップ)

ポップ

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		S.Top --; //Giam Top
		return S.Data[S.Top]; //Lay du lieu tai Top
	}
}

1.5 コー​​ド全体のプログラム (フル)

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

#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
	int Top; //Dinh Top
	item Data[Max]; //Mang cac phan tu
};

void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Isfull(Stack S); //kiem tra Stack day
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = 0; //Stack rong khi Top la 0
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == 0);
}

int Isfull(Stack S) //kiem tra Stack day
{
	return (S.Top == Max); //
}

void Push(Stack &S, item x) //them phan tu vao Stack
{
	if (!Isfull(S))
	{
		S.Data[S.Top] = x; //Gan du lieu
		S.Top ++; //Tang Top len 1
	}
}

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Data[S.Top-1]; //Lay du lieu tai Top
}

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		S.Top --; //Giam Top
		return S.Data[S.Top]; //Lay du lieu tai Top
	}
}

void Input (Stack &S)
{
	int n;
	item x;
	do
	{
		printf("Nhap so phan tu cua Stack (<%d) :",Max);
		scanf("%d",&n);
	} while (n>Max || n<1);
	for (int i=0; i<n; i++)
	{
		printf("Nhap phan tu thu %d : ", i+1);
		scanf("%d",&x);
		Push(S,x);
	}
}

void Output(Stack S)
{
	for (int i=S.Top-1; i>=0; i--)
		printf("%d   ",S.Data[i]);
	printf("\n");
}

int main()
{
    Stack S;
    Init(S);
    Input(S);
    Output(S);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Stack rong");
    printf("\n2: Kiem tra Stack day");
    printf("\n3: Them phan tu vao Stack");
    printf("\n4: Xoa phan tu trong Stack");
    printf("\n5: Xuat Stack");
    printf("\n6: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(S)) printf("Stack rong !");
				else printf ("Stack khong rong !");
				break;
			}
			case 2:
			{
				if (Isfull(S)) printf("Stack day !");
				else printf ("Stack chua day !");
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao DS: ");
				scanf("%d",&x);
				Push(S,x);
				break;
			}
			case 4:
			{
				Pop(S);
				break;
			}
			case 5: 
			{
				Output(S);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

リンクの冗長性

2. スタックカーソルにインストールされている

スタックポインタにスタックがまだ正常に機能しているが、それは、リンクを使用しているため、 ポインタ 割り当てて管理する, 過剰んか何かの欠如.

スタックポインタ

2.1 建築構造物

typedef int item; //kieu du lieu
struct Node
{
	item Data; //du lieu
	Node *Next; //link
};
typedef struct Stack
{
	Node *Top;
};

2.2 空のリストを初期化します, チェックリストは空です, 長リスト

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = NULL;
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == NULL);
}

int Len (Stack S)
{
	Node *P = S.Top;
	int i=0;
	while (P != NULL) //trong khi chua het Stack thi van duyet
	{
		i++;
		P = P->Next;
	}
	return i;
}

2.3 作る 1 ノード

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

2.4 スタックに挿入する要素 (押す)

まさにその点とトップノートのスタックポインタに要素を挿入するには, そして、それがトップ終了した時点

押す

void Push(Stack &S, item x) //them phan tu vao Stack
{
	Node *P = MakeNode(x);
	P->Next = S.Top;
	S.Top = P;
}

2.5 トップ上のデータを取得しますが、削除されていない (ピーク)

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Top->Data;
}

2.6 取り外し、上部のデータを取得する (ポップ)

一つは、カーソル位置のトップにのみポイントが必要 2 停止.

ポップ

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		item x = S.Top->Data; //luu lai gia tri
		S.Top = S.Top->Next; //Xoa phan tu Top
		return x;
	}
}

2.7 完全なプログラム (完全なコード)

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

typedef int item; //kieu du lieu
struct Node
{
	item Data; //du lieu
	Node *Next; //link
};
typedef struct Stack
{
	Node *Top;
};

void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Len (Stack S); //Do dai Stack
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack
Node *MakeNode(item x); //Tao 1 Node

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = NULL;
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == NULL);
}

int Len (Stack S)
{
	Node *P = S.Top;
	int i=0;
	while (P != NULL) //trong khi chua het Stack thi van duyet
	{
		i++;
		P = P->Next;
	}
	return i;
}

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

void Push(Stack &S, item x) //them phan tu vao Stack
{
	Node *P = MakeNode(x);
	P->Next = S.Top;
	S.Top = P;
}

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Top->Data;
}

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		item x = S.Top->Data; //luu lai gia tri
		S.Top = S.Top->Next; //Xoa phan tu Top
		return x;
	}
}

void Input (Stack &S) //nhap danh sach
{
    int i=0; 
    item x;
    do
    {
        i++;
        printf ("Nhap phan tu thu %d : ",i);
        scanf("%d",&x);
        if (x != 0) Push(S,x);
    } while(x != 0); //nhap 0 de ket thuc
}

void Output(Stack S)
{
	Node *P = S.Top;
	while (P != NULL)
	{
		printf("%d   ",P->Data);
		P = P->Next;
	}
	printf("\n");
}

int main()
{
    Stack S;
    Init(S);
    Input(S);
    Output(S);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Stack rong");
    printf("\n2: Do dai Stack");
    printf("\n3: Them phan tu vao Stack");
    printf("\n4: Xoa phan tu trong Stack");
    printf("\n5: Xuat Stack");
    printf("\n6: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(S)) printf("Stack rong !");
				else printf ("Stack khong rong !");
				break;
			}
			case 2:
			{
				printf("Do dai Stack: %d",Len(S));
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao DS: ");
				scanf("%d",&x);
				Push(S,x);
				break;
			}
			case 4:
			{
				Pop(S);
				break;
			}
			case 5: 
			{
				Output(S);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

リンクの冗長性

3. スタックを使用すると、C言語で利用可能です

C では、この方法を構築しています (顎) スタックに関連する, それだけで宣言して使用される

#include <iostream> // io
#include <stack> // use stack

using namespace std;

int main() {
	stack <int> S; // khai bao Stack voi kieu du lieu la int
	
	for (int i = 0; i < 10; i++) {
		S.push(i*78 + 26); // chen cac phan tu vao stack
	}
	
	cout << "Do dai stack: " << S.size() << "\n";
	
	// xuat tat ca phan tu trong stack
	while (!S.empty()) { 	// trong khi stack chua trong
		int x = S.top(); 	// lay gia tri top
		S.pop(); 			// loai bo khoi stack
		cout << x << "  ";
	}
	cout << "\n";
	
	return 0;
}

4. スタックの用途の例

スタックは、多くの用途を有している, 以下の通りである 1 の変換の応用. 次のコードは、ベースを転送します 10 ベースのxキーボード入力に

#include <iostream> // io
#include <stack> // use stack

using namespace std;

int main() {
	char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
	stack <char> S; // khai bao Stack voi kieu du lieu la int
	
	int coSo, so, du;
	
	cout << "Nhap so can chuyen: ";
	cin >> so;
	
	cout << "Nhap co so can chuyen: ";
	cin >> coSo;
	
	// chuyen doi bang cach dua vao Stack
	while(so) {
		du = so % coSo;
		S.push(num[du]);
		so /= coSo;
	}
	
	// Xuat ra
	while(!S.empty()) {
		cout << S.top();
		S.pop();
	}
	
	return 0;
}

[ポストをRPS-含ま=”2703″ ショートコード=”偽”]